package com.dbh.alg.algorithm.hot100.矩阵;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素
 *
 * 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
 * 输出：[1,2,3,6,9,8,7,4,5]
 *
 * 提示：
 * m == matrix.length
 * n == matrix[i].length
 * 1 <= m, n <= 10
 * -100 <= matrix[i][j] <= 100
 */
public class Leetcode54_螺旋矩阵 {


    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> order = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return order;
        }
        int row = matrix .length, column = matrix[0].length;
        int left = 0, right = column - 1, top = 0, bottom = row - 1;
        while (left <= right &&  top <= bottom) {
            // 第一行
            for (int c = left; c <= right; c++) {
                order.add(matrix[top][c]);
            }
            // 倒数第一列
            for (int r = top + 1; r <= bottom; r++) {
                order.add(matrix[r][right]);
            }
            // 判断不是单行单列的二维数组
            if (left < right &&  top < bottom) {
                // 最后一行
                for (int c = right - 1; c >= left; c--) {
                    order.add(matrix[bottom][c]);
                }
                // 第一列
                for (int r = bottom - 1; r > top; r--) {
                    order.add(matrix[r][left]);
                }
            }
            left++;
            right--;
            top++;
            bottom--;
        }
        return order;
    }


}
